/*
 * In August 1999, the following challange was posted to the internet
 * newsgroup: comp.arch.embedded
 *---------------------------------------------------------------------
 * WHICH IS BETTER - C or C++ ????
 *
 * This is a programming challenge in response to those of you who read
 * the "Nuts to OOP" article in Embedded Systems magazine and didn't
 * agree with it.
 *
 * Instead of shouting and arguing which language, C or C++, is better
 * (for embedded or otherwise), I have decided to make this challenge to
 * anyone that would dare say anything nice about C++.  It is possible
 * (albeit remotely) that a C++ programmer will accept this challenge and
 * win.  This challenge will make it possible for any C++ programmer to
 * PROVE to the world that C++ is better.  No zingers, no fowl language,
 * no name calling - just a programming challenge. 
 *
 * If anyone fails to accept this challenge, then they can't say for sure
 * that C++ is better than Real C can they?
 *
 * Attached is a PACMAN-like game programming example in Real C that I
 * have written specifically for this challenge. The program was written
 * in about 16 hours and is about 3K in size.  A successful challenger
 * will be able to clone the program in C++ with OOP in less time and
 * with fewer bytes.  You are encouraged to copy it and pass it on to
 * other C++ experts who might want to take on the challenge.
 *---------------------------------------------------------------------
 * The attached .ZIP file included C-MAN.COM at 3165 bytes, and the
 * following CHALENGE.TXT file:
 *---------------------------------------------------------------------
 * Take the Real C Challenge and Attempt to PROVE that C++ is Better!!
 *
 *
 * The enclosed program was written entirely in C.  It is a simple
 * PACMAN-like game and took me a whopping 16 hours to write and debug.
 * There was no assembly used with the exception of a few inline I/O
 * primitives.  The challenge is to write an identical version in C++
 * that is the same size or smaller than this one and also to write it
 * in the same or less time.
 *
 * This is a contest to determine which language is better to write
 * programs in - C or C++.  It is not a contest about assembler, forth,
 * pascal, or any other language.
 *
 * Failure of someone to provide a C++ clone of this program that is
 * smaller and developed in less time will serve to indicate that real
 * C is the winner and that C++ is the loser.
 *
 *
 * C-MAN Game Rules
 *
 * C-MAN is a PACMAN-like game that is played in a maze on the screen.
 * The keyboard moves the C-MAN player and the computer moves the
 * PLUSPLUS-MAN player.  When the program title screen is shown, press
 * any key to start the game.  The game can be aborted at any time by
 * pressing the ESCAPE key.
 *
 * C-MAN is a C programmer who starts out in the game with 4 jobs.  A job
 * is represented by a green dollar sign.  Whenever C-MAN takes a job, a
 * new job appears somewhere on the screen to replace the old job.  Also
 * on the board is PLUSPLUS-MAN who is a C++ progeammer.  PLUSPLUS-MAN is
 * after C-MAN's jobs and will roam around the screen looking for one of
 * them to steal.  The object of the game is for C-MAN to eat PLUSPLUS-MAN
 * before PLUSPLUS-MAN steals all of C-MAN's jobs.  Whenever C-MAN eats
 * PLUSPLUS-MAN, he gets a new job on the screen, but unfortunately, a
 * university some where spits out another PLUSPLUS-MAN to contend with.
 * The game is over when the user presses ESCAPE or PLUSPLUS-MAN steals all
 * of C-MAN's jobs.
 *
 *
 * The Basics
 *
 * This program is a COM file and runs under DOS or a DOS box under
 * Windows.  It was compiled in TINY model using Turbo C 2.0 with a
 * custom startup module.  The reason a COM file was chosen was because
 * it is the most compact of all executable files.  If you choose to
 * compete with an EXE, then your difficulty level is considerably
 * higher.  My program contains all of its data internal to itself
 * and does not utilize any external files.  Also, if you use any
 * library functions, you must include them as static libraries in
 * your final program.  Also, the sizes of any external data files
 * will be added to your file size total.
 *
 * In order to be valid, a competing C++ program must use Objects.
 *
 *
 * A Head Start
 *
 * I will not be releasing the source to my example until someone else
 * makes a bonafide C++ attempt at this challenge.  It took me 16 hours
 * to test and debug this thing.  Giving out the source would give others
 * an unfair advantage.  Nevertheless, I am willing to share some obvious
 * items that you may or may not be aware of.
 *
 * 1. The program runs under DOS and uses 320x200-256 VGA color graphics.
 *
 * 2. The keyboard functions are system BIOS calls.
 *
 * 3. With a program like this, there are several entities that a C++
 *    programmer might find OBJECT-able.  Also, this program uses a
 *    lot of tables that C++ is supposed to work better at than C.
 *
 * 4. The player called PLUSPLUS-MAN is controlled by a single neuron
 *    artificial intelligence subroutine.  In C, this is trivial.  He
 *    must be able to wander the screen in an intelligent manner.
 *    He must also have a certain degree of self preservation and be
 *    able to recognize danger when he sees it.  Unlike the human
 *    player, he cannot see through walls or objects.
 *
 * 5. It took me an hour or two just to design the graphics used in this
 *    program.  They are not very fancy and I am sure that just about
 *    anybody could do better.  Nevertheless, they are already done and
 *    in plain view for you to copy.
 *
 *
 * Conclusion
 *
 * This game is a programming example and is not intended to be of any
 * other value.  From a gaming perspective, it is rather dull compared
 * to just about any other computer game out there.
 *
 * In case it isn't obvious, the contest winner will be the language
 * that can write a C-MAN program with the smallest executable file
 * and in the least amount of time.
 *
 * If you intend to take me up on this challenge, let me know by email.
 * My address is: n4mwd@amsat.org
 *
 * Dennis Hawkins
 *---------------------------------------------------------------------
 * To date, no C++ programmer has taken him up on his challenge, however
 * I had been following the posting for a few days, and noted several
 * complaints about various aspects of the challenge... I felt it would
 * be useful to show the results of a C programmer developing to this
 * specification (which is what a C++ programmer would be doing), so I
 * wrote this program in Micro-C:
 *
 * When compiled with the standard Micro-C library, MCMAN.COM weighs in
 * at 3273 bytes, however since Dennis had removed the TC startup code
 * (which is over 1K), and rewritten several of the TC library functions,
 * I felt it was fair to trim the referenced library modules of functions
 * which were not actually used. This reduced the executable size to: 2873.
 * The unused functions are:
 *   LRG.ASM:
 *    lrg_getpal(), lrg_setpal(), lrg_fill(), lrg_hline(), lrg_vline(),
 *    lrg_draw(), lrg_erase(), lrg_scale() and lrg_retrace()
 *   MEMIO.ASM:
 *    peekw(), poke(), pokew(), in(), inw(), out(), outw()
 *
 * Noteworthy points of discussion:
 *   MCMAN is designed to closely mimic C-MAN's "look and feel"
 *   MCMAN is compiled with the standard Micro-C startup code
 *     (C-MAN compiled with standard TC startup is over 5k)
 *   MCMAN.C contains no inline assembly language or BIOS/DOS interrupts calls
 *     (It does use the BIOS 8x8 character set table)
 *     (C-MAN calls BIOS to write chars, MCMAN draws them using the table)
 *   MCMAN has smoother graphics than C-MAN, and is "flicker free"
 *   MCMAN is compiled for the 8088, C-MAN for the 80286
 *     (Compiling C-MAN for the 8088 adds about 250 bytes)
 *   MCMAN's ++MAN is a bit easier to catch (my kids complained)
 *   Total time to develop/debug MCMAN was about 4 hours.
 *
 * (The above is not intended to slight Dennis's code, which appears to be
 * quite well done - I would not have squeezed MCMAN nearly so much without
 * his program as a goal to beat - The above represents the fact that it is
 * much easier to improve on a design than to build it from scratch, and I
 * would expect a C++ programmer accepting the challenge to do the same).
 *
 * To compile the program with the standard library:
 *   cc mcman -fop
 * To compile with a trimmed LRG library:
 *   copy \mc\l_source\lrg.asm
 *   edit lrg.asm and memio.asm & remove above listed functions
 *   masm/ml lrg;
 *   masm/ml memio;
 *   cc mcman -fmop
 *   lc mcman lrg memio
 *
 * Dave Dunfield, Aug 22 - 1999
 */
#include <stdio.h>

#define	BIOS_ROM	0xF000		/* BIOS ROM segment */
#define	BIOS_CHR	0xFA6E		/* BIOS character set table offset */

/*
 * PC keyboard direction keys
 */
#define	UP		18432			/* UP arrow */
#define	DOWN	20480			/* DOWN arrow */
#define	LEFT	19200			/* LEFT arrow */
#define	RIGHT	19712			/* RIGHT arrow */

/*
 * Bits used in each maze entry
 */
#define	PASS	0x80			/* This is a passage */
#define	JOB		0x40			/* A job is here */
#define	TITLE	0x10			/* This is a title block */
#define	LMASK	0x08			/* Player can move LEFT from here */
#define	DMASK	0x04			/* Player can move DOWN from here */
#define	RMASK	0x02			/* Player can move RIGHT from here */
#define	UMASK	0x01			/* Player can move UP from here */

/*
 * Screen/Maze. This array defines the screen displays and maze travel.
 * See above for description of bits in each byte.
 */
unsigned char maze[10][16] = {
/* 0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15 */
0x86,0x9A,0x9A,0x9C,0x10,0x10,0x00,0x00,0x00,0x86,0x8A,0x8C,0x00,0x86,0x8A,0x8C,
0x95,0x00,0x00,0x85,0x00,0x86,0x8A,0x8C,0x00,0x85,0x00,0x85,0x00,0x85,0x00,0x85,
0x95,0x00,0x10,0x95,0x00,0x95,0x10,0x83,0x8A,0x99,0x00,0x85,0x10,0x85,0x00,0x95,
0x95,0x00,0x10,0x87,0x9A,0x8D,0x10,0x00,0x10,0x00,0x10,0x85,0x10,0x95,0x00,0x95,
0x95,0x00,0x96,0x89,0x10,0x83,0x9A,0x8E,0x9A,0x8C,0x10,0x87,0x9A,0x8D,0x10,0x95,
0x97,0x8A,0x99,0x00,0x00,0x00,0x10,0x85,0x10,0x95,0x10,0x85,0x10,0x85,0x00,0x95,
0x95,0x00,0x10,0x00,0x84,0x00,0x92,0x8D,0x10,0x85,0x10,0x85,0x10,0x85,0x00,0x95,
0x97,0x8A,0x9E,0x8A,0x8D,0x00,0x10,0x85,0x10,0x85,0x10,0x85,0x10,0x85,0x00,0x95,
0x95,0x00,0x85,0x00,0x85,0x00,0x86,0x89,0x00,0x85,0x00,0x85,0x00,0x85,0x00,0x85,
0x83,0x9A,0x9B,0x9A,0x9B,0x9A,0x89,0x00,0x00,0x83,0x8A,0x89,0x00,0x83,0x8A,0x89};

/*
 * Unpacked sprite storage (for lrg_blit() function)
 */
char
	cman1[20][20],		/* C-MAN with his mouth open */
	cman2[20][20],		/* C-MAN with his mouth shut */
	ppman[20][20],		/* ++MAN */
	job[20][20],		/* A Job */
	white[20][20],		/* An empty slot */
	green[20*6][20*2];	/* Message box at end of game */

/*
 * Packed sprites...
 * First entry is color, remaining entries are horizontal row patterns.
 */
unsigned _cman1[20] = {
	1,		 /* Blue */
	0x0000,  /* 0000000000000000 */
	0x0FF0,  /* 0000111111110000 */
	0x1FF8,  /* 0001111111111000 */
	0x381C,  /* 0011100000011100 */
	0x7006,  /* 0111000000000110 */
	0x6002,  /* 0110000000000010 */
	0xC000,  /* 1100000000000000 */
	0xC000,  /* 1100000000000000 */
	0xC000,  /* 1100000000000000 */
	0xC000,  /* 1100000000000000 */
	0xC000,  /* 1100000000000000 */
	0xC002,  /* 1100000000000010 */
	0x6006,  /* 0110000000000110 */
	0x7006,  /* 0111000000000110 */
	0x381C,  /* 0011100000011100 */
	0x1FF8,  /* 0001111111111000 */
	0x0FF0,  /* 0000111111110000 */
	0x0000}; /* 0000000000000000 */
unsigned _cman2[20] = {
	1,		 /* Blue */
	0x0000,  /* 0000000000000000 */
	0x0FE0,  /* 0000111111100000 */
	0x1FF0,  /* 0001111111110000 */
	0x3838,  /* 0011100000111000 */
	0x700C,  /* 0111000000001100 */
	0x6006,  /* 0110000000000110 */
	0xC002,  /* 1100000000000010 */
	0xC000,  /* 1100000000000000 */
	0xC000,  /* 1100000000000000 */
	0xC000,  /* 1100000000000000 */
	0xC002,  /* 1100000000000010 */
	0xC006,  /* 1100000000000110 */
	0x6006,  /* 0110000000000110 */
	0x700C,  /* 0111000000001100 */
	0x3838,  /* 0011100000111000 */
	0x1FF0,  /* 0001111111110000 */
	0x0FE0,  /* 0000111111100000 */
	0x0000}; /* 0000000000000000 */
unsigned _ppman[20] = {
	4,		 /* Red */
	0x0C00,  /* 0000110000000000 */
	0x0C00,  /* 0000110000000000 */
	0x0C00,  /* 0000110000000000 */
	0x0C00,  /* 0000110000000000 */
	0xFFC0,  /* 1111111111000000 */
	0xFFC0,  /* 1111111111000000 */
	0x0C00,  /* 0000110000000000 */
	0x0C30,  /* 0000110000110000 */
	0x0C30,  /* 0000110000110000 */
	0x0C30,  /* 0000110000110000 */
	0x0030,  /* 0000000000110000 */
	0x03FF,  /* 0000001111111111 */
	0x03FF,  /* 0000001111111111 */
	0x0030,  /* 0000000000110000 */
	0x0030,  /* 0000000000110000 */
	0x0030,  /* 0000000000110000 */
	0x0030,  /* 0000000000110000 */
	0x0000}; /* 0000000000000000 */
unsigned _job[20] = {
	2,		 /* Green */
	0x0080,  /* 0000000010000000 */
	0x03E0,  /* 0000001111100000 */
	0x0EB8,  /* 0000111010111000 */
	0x188C,  /* 0001100010001100 */
	0x1084,  /* 0001000010000100 */
	0x1080,  /* 0001000010000000 */
	0x1880,  /* 0001100010000000 */
	0x0C80,  /* 0000110010000000 */
	0x07F8,  /* 0000011111111000 */
	0x008C,  /* 0000000010001100 */
	0x0086,  /* 0000000010000110 */
	0x0082,  /* 0000000010000010 */
	0x0082,  /* 0000000010000010 */
	0x1886,  /* 0001100010000110 */
	0x0C9C,  /* 0000110010011100 */
	0x07F0,  /* 0000011111110000 */
	0x0080}; /* 0000000010000000 */

/*
 * Misc global variables
 */
unsigned
	cmx,			/* C-MAN X position */
	cmy,			/* C-MAN Y position */
	pmx = 20*15,	/* ++MAN X position */
	pmy,			/* ++MAN Y position */
	cmd,			/* C-MAN Moveing direction */
	pmd,			/* ++MAN Moveing direction */
	rand_seed,		/* Random number seed */
	jcount;			/* Count of active jobs */

/*
 *								  1
 * Direction->delta axis tables: 402
 *								  3
 */
int delta_x[] = { 0, 0, 1, 0, -1};
int delta_y[] = { 0, -1,0, 1, 0 };

/*
 * Table of allowed direction masks in maze table.
 */
unsigned char dir_mask[] = { 0x0F, UMASK, RMASK, DMASK, LMASK };

/*
 * Initialize a sprite to all one color
 */
init_sprite(char *m, int c, unsigned s)
{
	do
		*m++ = c;
	while(--s);
}

/*
 * Extract a packed sprite into a memory image
 */
void unpack_sprite(char data[20][20], unsigned pack[])
{
	unsigned x, y, v, c;

	init_sprite(data, 7, sizeof(data));
	c = pack[y=0];
	do {
		v = pack[++y];
		x = 1;
		do {
			if(v & 0x8000)
				data[y][x] = c;
			v <<= 1; }
		while(++x <= 16); }
	while(y < 18);
}

/*
 * Get pseudo-random number and impose limit
 */
unsigned random(unsigned range)
{
	return (rand_seed = (rand_seed * 13709) + 13849) % range;
}

/*
 * Find a free passageway location in the maze
 */
void find_free(int *x, int *y)
{
	while((maze[*y = random(10)][*x = random(16)] & (PASS|JOB)) != PASS);
}

/*
 * Add a new job to the maze
 */
void add_job()
{
	unsigned x, y;
	find_free(&x, &y);
	maze[y][x] |= JOB;
	lrg_blit(x*20, y*20, 20, 20, job);
	++jcount;
}

/*
 * Attempt to move a player, stop him and report of he hits a wall.
 */
int move(unsigned *xx, unsigned *yy, unsigned md)
{
	unsigned x, y;
	x = *xx;
	y = *yy;
	if((x % 20) || (y % 20)) {
		*xx = x + delta_x[md];
		*yy = y + delta_y[md];
		return 0; }
	if(!(maze[y/20][x/20] & dir_mask[md]))
		return -1;
	*xx += delta_x[md];
	*yy += delta_y[md];
	return 0;
}

/*
 * Move the ++MAN, giving (a very low amount of) intelligence
 */
void ppman_move()
{
	unsigned x, y, d, c;
	unsigned char *m;
	static unsigned char run;

	/* Move ++MAN, if stuck, select a new direction */
	if(move(&pmx, &pmy, pmd))
		goto new_direct;
	/* No further processing unless we are at a block boundary */
	if((pmy % 20) || (pmx % 20))
		return;
	/* Handle any jobs we might find here */
	if(*(m = maze[pmy/20]+(pmx/20)) & JOB) {
		--jcount;
		*m &= ~JOB; }

	/* Very simple detection of C-MAN, change direction if C-MAN
	 * is in an adjacent square. This remains fair to the "++MAN
	 * cannot see through walls" rule, because only one square of
	 * detection is performed, so C-MAN must be right beside ++MAN,
	 * or 1 cell diagonal which would be visible in a real maze. */
	if((abs(cmy - pmy) < 40) && (abs(cmx - pmx) < 40)) {
		if(run)
			return;
		d = pmd;
		run = -1;
		++pmd;
		goto new_direct1; }

	/* Detect intersections, and allow a directional change */
	run = 0;
	switch(*m & (UMASK|RMASK|DMASK|LMASK)) {
		case RMASK|LMASK:	/* Left/Right hallway */
		case UMASK|DMASK:	/* Up/Down hallway */
			return; }

new_direct:
	d = ((pmd+1)&3)+1;	/* Avoid returning to same direction */
	pmd = random(19)&3;
new_direct1:
	x = pmx/20;
	y = pmy/20;
	c = 6;
	do {
		if(!--c)
			d = -1;
		pmd = (pmd & 3)+1; }
	while((pmd == d) || !(maze[y][x] & dir_mask[pmd]));
}

/*
 * Enter graphics mode and draw an initial screen
 */
void draw_screen(unsigned char mask)
{
	unsigned x, y;
	/* Draw the screen */
	lrg_open();
	x = 0;
	do {
		y = 0;
		do {
			if(maze[y][x] & mask)
				lrg_blit(x*20, y*20, 20, 20, white); }
		while(++y < 10); }
	while(++x < 16);
}

/*
 * Draw a string beginning at the specified co-ordinates
 * (We write our own function here instead of using the one from
 * the LRG library, since it carres several other functions in it's
 * module which we do not need.
 */
void lrg_puts(unsigned x, unsigned y, unsigned c, char *s)
{
	int i, j, b, ci;
	while(*s) {
		ci = (*s++ << 3) + BIOS_CHR;
		for(i=0; i < 8; ++i) {
			b = peek(BIOS_ROM,ci++);
			for(j=0; j < 8; ++j) {
				lrg_plot(x+j, y+i, (b & 0x80) ? c : c >> 8);
				b <<= 1; } }
		x += 8; }
}

/*
 * Main program
 */
main()
{
	unsigned x, y, i, j, d;

	/* Create the solid white sprite */
	init_sprite(white, 7, sizeof(white));

	/* Unpack the initial sprites */
	unpack_sprite(cman1, _cman1);
	unpack_sprite(cman2, _cman2);
	unpack_sprite(ppman, _ppman);
	unpack_sprite(job, _job);

	/* Display the startup screen, wait for a key */
	draw_screen(TITLE);
	lrg_puts(35, 200-35, 2, "A programming example in real C");
	lrg_puts(125, 200-20, 4, "(C) 1999 Dave Dunfield");
	lrg_puts(125, 200-10, 4, "<www.dunfield.com>");
	kbget();
	lrg_close();

	/* Draw the maze screen and add the initial jobs */
	draw_screen(PASS);
	add_job();
	add_job();
	add_job();
	add_job();

	/* Loop, moving ++MAN and C-MAN, until game ends */
	do {
		/* Erase ++MAN, move him, redraw him */
		lrg_blit(pmx, pmy, 20, 20, white);
		i = ((cmx == pmx) && (cmy == pmy));
		ppman_move();
		lrg_blit(pmx, pmy, 20, 20, ppman);
		/* If ++MAN gets eaten, replace him, and add a job */
		if(i || ((cmx == pmx) && (cmy == pmy))) {
			find_free(&pmx, &pmy);
			pmx *= 20;
			pmy *= 20;
			add_job(); }
		/* Draw C-MAN and wait a bit to set speed */
		lrg_blit(cmx, cmy, 20, 20, ++j & 0x08 ? cman1 : cman2);
		lrg_delay(1);
		/* Buffer directional keys, detect exit condition */
		if(kbhit())
			if((d = kbget()) == 0x1B)
				break;
		/* Erase C-MAN and move him */
		lrg_blit(cmx, cmy, 20, 20, white);
		move(&cmx, &cmy, cmd);
		if((cmx % 20) || (cmy % 20))
			continue;
		/* Update actual C-MAN direction only at a cell boundary */
		switch(d) {
			case UP:	cmd = 1;	break;
			case RIGHT:	cmd = 2;	break;
			case DOWN:	cmd = 3;	break;
			case LEFT:	cmd = 4;	}
		/* If C-MAN takes a job, add a new one */
		if(maze[y = cmy/20][x = cmx/20] & JOB) {
			add_job();
			maze[y][x] &= ~JOB;
			--jcount; }	 }
	while(jcount);

	/* Display end message, wait for a key, terminate graphics & exit */
	init_sprite(green, 2, sizeof(green));
	lrg_blit(20*6, 20*4, 20*5, 20*2, green);
	lrg_puts(135, 96, 0x0200, "GAME OVER");
	lrg_delay(60);
	kbget();
	lrg_close();
}
